//
//  Copyright 2015 XiaoJSoft Studio.
//  Copyright 2015 Harbin Institute of Technology(HIT), Software Engineering Department.
//
//  Use of this source code is governed by a proprietary license. You can not read, change or
//  redistribute this source code unless you have a written authorization from the copyright
//  holder listed above.
//

#include "graph.h"
#include <new>
#include <queue>

namespace ui {
namespace compiler {

DirectedGraph::DirectedGraph(const unsigned int vertex_count) {
    //  Load the vertex count.
    this->m_VertexCount = vertex_count;

    //  Initialize the links table.
    this->m_Links.clear();
    for (unsigned int idx = 0; idx < vertex_count; ++idx) {
        this->m_Links.push_back(std::vector<unsigned int>());
    }
}

DirectedGraph::~DirectedGraph() {
    //  Dummy.
}

void DirectedGraph::addEdge(const unsigned int source_vertex, const unsigned int target_vertex) {
    this->m_Links[source_vertex].push_back(target_vertex);
}

unsigned int DirectedGraph::getVertexCount() {
    return this->m_VertexCount;
}

void DirectedGraph::getAdjacentVertexes(const unsigned int vertex_id, std::vector<unsigned int> &output) {
    output = this->m_Links[vertex_id];
}

bool DirectedGraph::doToposort(std::vector<unsigned int> &output) {
    //  Special check for the condition of no vertex.
    if (this->getVertexCount() == 0) {
        output.clear();
        return true;
    }

    //  Allocate an array to contain the in-degree values.
    int *in_degrees = new int[this->getVertexCount()];
    if (!in_degrees) {
        throw std::bad_alloc();
    }

    //  Clear in-degree values.
    for (unsigned int idx = 0; idx < this->getVertexCount(); ++idx) {
        in_degrees[idx] = 0;
    }

    //  Calculate in-degree values.
    for (unsigned int source_id = 0; source_id < this->getVertexCount(); ++source_id) {
        //  Get adjacent vertexes.
        std::vector<unsigned int> adjacent;
        this->getAdjacentVertexes(source_id, adjacent);

        //  Increase the in-degree value of each target vertex.
        for (std::vector<unsigned int>::iterator target_vertex = adjacent.begin(); target_vertex != adjacent.end(); ++target_vertex) {
            in_degrees[*target_vertex]++;
        }
    }

    //  Initialize an empty queue.
    std::queue<unsigned int> vertex_queue;
    while(!vertex_queue.empty()) {
        vertex_queue.pop();
    }

    //  Push all vertexes whose in-degree value is zero to the queue.
    for (unsigned int idx = 0; idx < this->getVertexCount(); ++idx) {
        if (in_degrees[idx] == 0) {
            vertex_queue.push(idx);
        }
    }

    //  Clear the output container.
    output.clear();

    //  Toposort.
    while(!vertex_queue.empty()) {
        //  Pop an vertex off from the head of the queue.
        unsigned int current_vertex = vertex_queue.front();
        vertex_queue.pop();

        //  Get its adjacent vertexes.
        std::vector<unsigned int> adjacent;
        this->getAdjacentVertexes(current_vertex, adjacent);

        //  Remove the vertex.
        //  (Decrease the in-degree value of each target vertex. When the value equals to 0, push the target vertex to the tail of the queue.)
        for (std::vector<unsigned int>::iterator target_vertex = adjacent.begin(); target_vertex != adjacent.end(); ++target_vertex) {
            if (--in_degrees[*target_vertex] == 0) {
                vertex_queue.push(*target_vertex);
            }
        }

        //  Add the vertex to output container.
        output.push_back(current_vertex);
    }

    //  Check whether there are some vertexes remained. If so, toposorting will be failed.
    for (unsigned int idx = 0; idx < this->getVertexCount(); ++idx) {
        if (in_degrees[idx] != 0) {
            //  Clear memories.
            delete[] in_degrees;

            return false;
        }
    }

    //  Clear memories.
    delete[] in_degrees;

    return true;
}

}  //  namespace compiler
}  //  namespace ui
